package com.lisp.algorithm.sort;

import java.util.Arrays;

import com.lisp.algorithm.util.SortUtil;

public class CountingSort {

    /*
    1. 新建辅助数组tmp[], 用tmp[a[i]]记录值a[i]出现的次数
    2. 从0开始，统计<=a[i]元素个数，记录到tmp[a[i]]，即：tmp[i+1] = tmp[i+1]+tmp[i]
    3. 遍历tmp数组，for i -> tmp.length { repeat (tmp[i], a[j++]=i); }
    */
    
    public static void main(String[] args) {
        SortUtil.test(CountingSort::countingSort2);
    }
    
    private static final int MAX_VAL = 100;
    
    /** 这种写法只能用于数字排序，严格来说，不能算是一种正确的排序方法 */
    public static void countingSort(int a[]) {
        int tmp[] = new int[MAX_VAL+1];
        for(int val : a) {
            tmp[val]++;
        }
        
        for(int i=1; i<tmp.length; i++) {
            tmp[i] = tmp[i] + tmp[i-1];
        }
        
        int prevVal = 0;
        int aIndex = 0;
        for(int i=0; i<tmp.length; i++) {
            for(int j=tmp[i]; j>prevVal; j--) {
                a[aIndex++] = i;
            }
            prevVal = tmp[i];
        }
    }
    
    /** 排序是稳定的 */
    private static void countingSort2(int a[]) {
        int tmp[] = new int[MAX_VAL+1];
        for(int val : a) {
            tmp[val]++;
        }
        
        for(int i=1; i<tmp.length; i++) {
            tmp[i] = tmp[i] + tmp[i-1];
        }
        
        int copy[] = Arrays.copyOf(a, a.length);
        for(int j=copy.length-1; j>=0; j--) {
            a[tmp[copy[j]]-1] = copy[j];
            tmp[copy[j]]--;
        }
    }
}
